package com.sicheng.蓝桥.练习题.dp;

import java.util.Scanner;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/5/22 11:53
 */
@SuppressWarnings("all")
public class 区间最值rmq {
    static int n;
    static int[] a;
    //dp[i][j] 表示以i开始,往后数2^j个元素的子区间
    static int[][] dp;

    //预处理O（nlogn）
    static void rmq() {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        dp = new int[n + 1][n + 1];
        a = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            a[i] = scanner.nextInt();
        }
        for (int i = 1; i <= n; i++) {
            dp[i][0] = a[i];
        }
        //区间下标起始值用1
        //从i开始 右端点i+2^j-1
        //大致思路就是先固定区间长为2^j,更新每一个起点i，以i开始区间长度是2^j
        //意味着 实际就是区间[i,i+2^j-1]的最值是2个区间拼凑起来的
        //从i开始数2^(j-1)所覆盖的区间 ,和从区间右端点往左数2^(j-1)所覆盖的区间
        // [i,i+2^(j-1)], [i + 2^(j-1), i+2^j-1]=========>dp[i][j-1],dp[i + (1 << (j - 1))][j-1]
        //实际例子
        // 1,3,1,2
        //区间长为2^0=1时,   [1,1]=1 [2,2]=3 [3,3]=1 [4,4]=2
        //当区间长为2^1时,   [1,2]=min{[1,1],[2,2]}=1, [2,3]=min{[2,2],[3,3]}=1,[3,4]=min{[3,3][4,4]}=1
        //当区间长为2^2时，   [1,4]=min{[1,2],[3,4]}=1
        for (int j = 1; (1 << j) <= n; j++) {
            for (int i = 1; i + (1 << j) - 1 <= n; i++) {
                dp[i][j] = Math.min(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
            }
        }
    }

    //查询 O（1）
    static int query(int l, int r) {
        int k = (int) (Math.log(r - l + 1) / Math.log(2));
        return Math.min(dp[l][k], dp[r - (1 << k) + 1][k]);
    }

    public static void main(String[] args) {
        //输入
        //4
        //1 3 1 4
        rmq();
        System.out.println(query(2, 4));
    }

}
